package com.favorite;

import java.util.ArrayList;
import java.util.List;

public class Solution1382 {
    List<Integer> list = new ArrayList<>();
    public TreeNode balanceBST(TreeNode root) {
        getArray(root);
        int[] arr = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            arr[i] = list.get(i);
        }
        return buildTree(arr, 0, arr.length - 1);
    }

    public void getArray(TreeNode root) {
        if (root == null) return;
        getArray(root.left);
        list.add(root.val);
        getArray(root.right);
    }

    public TreeNode buildTree(int[] arr, int l, int r) {
        if (l > r) return null;
        if (l == r) return new TreeNode(arr[l]);
        int mid = (l + r) >> 1;
        TreeNode root = new TreeNode(arr[mid]);
        root.left = buildTree(arr, l, mid - 1);
        root.right = buildTree(arr, mid + 1, r);
        return root;
    }
}
